//
// Created by Administrator on 2021/8/11.
//
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <string>
#include <climits>
#include <numeric>

using namespace std;

class Solution {
public:
    int canCompleteCircuit(vector<int> &gas, vector<int> &cost) {
        int n = (int) gas.size();
        vector<int> gain(n, 0);
        int sum = 0;
        for (int i = 0; i < n; ++i) {
            gain[i] = gas[i] - cost[i];
            sum += gain[i];
        }
        if (sum < 0)
            return -1;
        for (int i = 0; i < n; ++i) {
            if (gain[i] >= 0) {
                int curSum = gain[i];
                bool flag = true;
                for (int j = 1; j <= n; ++j) {
                    int index = (i + j) % n;
                    curSum += gain[index];
                    if (curSum < 0) {
                        flag = false;
                        break;
                    }
                }
                if (flag)
                    return i;
            }
        }
        return -1;
    }
    // AC 30%
};

class Solution2 { // 题解 一次遍历
public:
    /**
     * 假设从 i 到 k 是一次失败的路径
     * j 是 i , k  中间一点
     * 能够到达j，说明到j处时的油量>=0;
     * 无法到达k,说明从j到k的耗油总量大于得油总量，即从j开始也无法进行一次成功得行走
     * 所以下一次可以直接从k开始尝试
     * @param gas
     * @param cost
     * @return
     */
    int canCompleteCircuit(vector<int> &gas, vector<int> &cost) {
        int n = gas.size();
        int i = 0;
        while (i < n) {
            int sumOfGas = 0, sumOfCost = 0;
            int cnt = 0; // 记录走了几个加油站
            while (cnt < n) {
                int j = (i + cnt) % n;
                sumOfGas += gas[j];
                sumOfCost += cost[j];
                if (sumOfCost > sumOfGas) {
                    break; // 走到无法到达为止
                }
                cnt++;
            }
            if (cnt == n) {
                return i;
            } else {
                i = i + cnt + 1; // 下一次从无法到达的位置开始出发
            }
        }
        return -1;
    }
};

int main() {
    vector<int> gas{1, 2, 3, 4, 5};
    vector<int> cost{3, 4, 5, 1, 2};
    Solution solution;
    cout << solution.canCompleteCircuit(gas, cost) << endl;
    return 0;
}
